/***************************************************************************
 *   Copyright (C) 2007 by Warren Kenny   				   *
 *   warren.kenny@gmail.com   						   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef GS_LINKED_LIST_H
#define GS_LINKED_LIST_H

#include <gsCore/gsCore.h>
#include <gsCore/gsException.h>

#include <gsContainer/gsContainer.h>
#include <gsContainer/gsLink.h>

/**
 *	A class which represents a linked-list data structure
 *	gsLinkedList has been optimized for linear iteration, if you require a data container which resizes and 
 *	linearly iterates in constant time then this container type is ideal
 */

template<class T>
class gsLinkedList : public gsContainer<T>
{
public:
	///
	/// Constructor(s)
	///
	
	/**
	 *        Default constructor
	 */
	gsLinkedList();

	/**
	 *        Constructor, takes another gsLinkedList as a parameter and duplicates its contents
	 * @param other The other gsLinkedList
	 */
	gsLinkedList( const gsLinkedList<T>& other );

	/**
	 *        Constructor, takes a \b single-dimension gsContainer as a paramter and duplicates its contents
	 * @param container The gsContainer
	 */
	gsLinkedList( const gsContainer<T>& container );
	
	/// 
	///	Overridden Method(s)
	///
	
	/**
	 * 	Generic method for inserting an object into the container; overrided from gsContainer
	 * @param object The object to be inserted
	 * @return 	- True is the object was successfully inserted
	 *		- False otherwise
	 */
	virtual gsBool insert( const T& object );
	
	/**
	 * 	Generic method for removing an object from the container; overrided from gsContainer
	 * @param object The object to be removed
	 * @return 	- True if the object was found and removed successfully
	 *		- False otherwise
	 */
	virtual gsBool remove( const T& object );
	
	/**
	 * 	Generic function for indicating whether a given object exists within the container; overrided from gsContainer
	 * @param object The object to be found
	 * @return 	- True if the object was found
	 *		- False otherwise
	 */
	virtual gsBool find( const T& object );
	
	/**
	 *        Generic function for retrieving an object from the specified index within the container; overrided from gsContainer
	 * @param index The index within the container from which the object should be retrieved
	 * @param[out] object A reference to the object to be set
	 * @return 	- True if the object was retrieved
	 *		- False otherwise
	 */
	virtual gsBool get( const gsUInt index, T& object );
	
	/**
	 *	Generic function for indicating whether the container is empty, overrided from gsContainer
	 * @return 	- True if the container is empty
	 *		- False if the container holds one or more objects
	 */
	virtual gsBool empty();
	
	/**
	 *	Generic function for finding the number of elements in the container; overrided from gsContainer
	 * @return	The number of elements in the container 
	 */
	virtual const gsUInt getSize();
	
	/**
	 *        Generic function for finding the current storage capacity of the container; overrided from gsContainer
	 * @return 	The storage capacity of the container
	 */
	virtual const gsUInt getCapacity();	
	
	/**
	 *        Generic function for removing all objects from the container and setting its storage capacity to zero,
	 *	  overridden from gsContainer
	 */
	virtual void clear();
	
	///
	///	Overridden Operator(s)
	///
	
	/**
	 *        Assignment operator, copies the contents of \a other and returns a reference to the
	 * 	  resulting object
	 * @param other The other gsLinkedList
	 * @return A reference to the produced gsLinkedList object
	 */
	gsLinkedList<T>& operator=( gsLinkedList<T>& other );

	/**
	 *        Assgnment operator, copies the contents of \a container and returns a reference to the 
	 * 	  resulting gsLinkedList object
	 * @param container The gsContainer to be duplicated
	 * @return A reference to the gsLinkedList with the same contents as the given container
	 */
	gsLinkedList<T>& operator=( gsContainer<T>& container );

	/**
	 *        Compares two gsLinkedList objects. Two gsLinkedLists are identical if they contain the 
	 *	  same objects in the same sequence
	 * @param other The other gsLinkedList
	 * @return 	True - If the provided gsLinkedList is identical to this one
	 *		False - Otherwise
	 */
	gsBool operator==( gsLinkedList<T>& other );
	
	/**
	 * 	 Compares a gsContainer to this gsLinkedList. The gsContainer is identical to this gsLinkedList
	 *	 only if it contains the same objects in the same sequence 
	 * @param container The gsContainer
	 * @return 	True - If the provided gsContainer is identical to this gsLinkedList
	 *		False - Otherwise
	 */
	gsBool operator==( gsContainer<T>& container );
	
	/**
	 *        Overloaded operator, retrieves the object at the specified index within the linked list
	 *	  \b Warning: For random selections, this operation will require \b index operations to perform
	 *	  However, for linear iteration, this will be equivalent in speed to standard array iteration
	 * @param index The index within the linked list from which to retrieve the object
	 * @return Reference to the stored object
	 */
	T& operator[]( const gsUInt index ) throw( gsArrayIndexOutOfBoundsException );
	
	/**
	 *        Overloaded operator, retrieves a constant reference to the object at the specified index within the linked list
	 *	  \b Warning: For random selections, this operation will require \b index operations to perform
	 *	  However, for linear iteration, this will be equivalent in speed to standard array iteration
	 * @param index The index within the linked list from which to retrieve the object
	 * @return Constant reference to the stored object
	 */
	const T& operator[]( const gsUInt index ) const throw( gsArrayIndexOutOfBoundsException );
	
	///
	///	Native Method(s)
	///
	
	

	///
	///	Destructor(s)
	///
	
	/**
	 *        Default destructor
	 */
	~gsLinkedList();

protected:
	
	/**
	 *        Protected method; retrieves the gsLink at the specified index within the list
	 * @param index The index of the gsLink within the list
	 * @return The gsLink
	 */
	gsLink<T>* getLink( gsUInt index ); 
	
	/**
	 *        Removes the given link from the linked list
	 * @param target the gsLink to be removed from the list
	 */
	void removeLink( gsLink<T>* target );
	
	gsLink<T>* m_head;
	gsLink<T>* m_tail;
	
	gsUInt m_size;
	
	gsLink<T>* m_history;
	gsUInt m_historyIndex;
};


#include <gsContainer/gsLinkedList.inl>

			 
#endif /// GS_LINKED_LIST_H

